package com.example.leetcode;

public class Sort {
    public static void main(String[] args) {
        int[] a = {1,7,2,4,3,5};
        printArr(a);
        sort(a);
        printArr(a);

    }

    public static void sort(int[] arr) {
        quickSort(0,arr.length-1,arr);
    }

    public static void quickSort(int start, int end, int[] arr) {
        if (start >= end) {
            return;
        }
        int left = start;
        int right = end;
        int comparedNum = arr[start];
        while (left < right) {
            while (left < right && comparedNum < arr[right]) {
                right--;
            }
            while (left < right && comparedNum > arr[left]) {
                left++;
            }
            swap(left,right,arr);
//            if (arr[left] == arr[right] && (left < right)) {
//                left++;
//            } else {
//                swap(left,right,arr);
//            }
        }
        quickSort(start, left - 1, arr);
        quickSort(left + 1, end, arr);
    }

    public static void printArr(int[] arr) {
        for (int i: arr) {
            System.out.println(i);
        }
    }

    public static void swap(int l, int r, int[] arr) {
        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }
}
